Referring to FIG. 1, in some computer networks each data packet 100 transmitted over the network is fragmented into smaller cells 110 (herein called data cells) for transmission over the network. Furthermore, as shown in FIG. 2, the data cells of different packets (e.g., packets simultaneously arriving at a particular host computer 120 (Host D) from different nodes 122, 124, 126 in the network) may be interleaved on the same network cable 128.
An example of such a network is any Asynchronous Transfer Mode (ATM) network. As shown in FIG. 1, in ATM networks, packets are transmitted in the form of data cells 110, each of which is 53 bytes long, including a five-byte header 130 and a 48-byte data portion 132. Each data cell's header 130 includes a "virtual circuit identifier" 134, discussed below, and a END flag 136 that is set only for the last cell of each data packet. For the purposes of this document, it can be assumed that there is no particular relationship between cell boundaries and either (A) the boundary between the "packet header" 138 and "packet body" 140, or (B) the boundary between the encrypted and unencrypted portions of the data packet 100.
For security reasons, data packets are usually encrypted using a public or private key encryption methodology. Furthermore, to ensure data integrity, a CRC error detection code is included in each packet, usually at the end of the packet, for detecting corrupted packets as well as for detecting packets that may have been tampered with in an attempt to break the system's security provisions. Therefore each packet received by the network controller must be decrypted and error checked by a CRC (cyclic redundancy check) circuit before it can be used by the host computer. However, it should be noted that the present invention is also applicable to networks carrying unencrypted data packets.
In ATM networks there is usually an upper bound on the size of any one packet, such as 4K (4096) bytes, or perhaps 10,000 bytes. However, a very large number of packets can be interleaved at any one network controller (receiver).
The problem presented by interleaved, fragmented packets is how to make a network controller (i.e., the interface between a workstation or other host computer and the network cables) that can decrypt and CRC check these packets. Data packets are usually decrypted and CRC checked as a whole because it would be expensive to provide the support circuitry needed to multiplex commercially available CRC circuits so as to process interleaved packet portions. Assuming that a packet must be processed as a whole, the network controller will need to buffer all incoming packets, and then decrypt and CRC check each packet after the end of the packet is received. However, since there is virtually no upper bound on packet interleaving, the amount of buffer space needed in the network controller to handle incoming packets is virtually limitless.
One potential method of avoiding the need for unlimited buffer space in the network controller is to discard one or more incomplete data packets when the network controller buffer overflows. While discarding packets, by itself, is probably tolerable in most computer systems if it happens infrequently, it is much less tolerable when the host computer is unable to pick which packets to discard. Since some packets are more important for correct functioning of the system than others, an uninformed selection of which packets to discard by the network controller may cause disruption of the computer network.